동적 배열

메모리에 데이터를 저장하는 영역에 스택과 힙이 있음.

스택은 스택 프레임 쌓이는 메모리 공간이고, 힙은 변수의 생성시기와 소멸시기를 프로그래머가 결정할 수 있는 메모리가 동적으로 할당 되는 영역이다.

스택 프레임을 할당하려면 고정된 크기를 가져야해서 크기가 가변적으로 변할 수 있는 상황에서는 스택에 할당못함요.

동적배열이란, 힙 영역에 저장되는 배열을 의미한다.

배열은 메모리에서 연속적으로 위치한다

→ 메모리에서 가져올 때 매번 요청하면 너무 손해다. 배열을 모두 캐시에 가져와서 빠르게 사용.

조회

조회에 경우 인덱싱을 통해서 O(1)

끝에 삽입

• 배열이 차지 않았을 경우 : O(1)
• 배열이 다 찼을 경우 : O(n)

→ 분할 상환 분석에 따라서, n개 까지 찰때까지는 O(1) 그 이후에 한번만 O(n) 이므로 전체 연산은 O(1) 라고 할 수 있다.

배열 중간에 데이터 삽입, 삭제

뒤에 있는 요소들을 모두 이동해야해서 O(n)